package com.yun.algorithm.backtracking.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class leetcode40 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, new boolean[candidates.length], target, 0, new LinkedList<>(), result);
        return result;
    }

    private void dfs(int[] candidates, boolean[] visited, int target, int start,
                     LinkedList<Integer> stack,
                     List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(stack));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            int candidate = candidates[i];
            if (target < candidate) {
                continue;
            }
            if (i > 0 && candidate == candidates[i - 1] && !visited[i - 1]) {
                continue;
            }
            visited[i]=true;
            stack.push(candidate);
            dfs(candidates, visited, target - candidate, i + 1, stack, result);
            stack.pop();
            visited[i]=false;
        }
    }

    public List<List<Integer>> combinationSum3(int[] candidates, int target){
        int[] buckets=new int[51];
        for (int candidate : candidates) {
            buckets[candidate]++;
        }
        List<List<Integer>> result = new ArrayList<>();
        dfs2(buckets,target,1,new LinkedList<>(),result);
        return result;
    }

    private void dfs2(int[] buckets,int target,int start,
                      LinkedList<Integer> stack,
                      List<List<Integer>> result){
        if (target == 0) {
            result.add(new ArrayList<>(stack));
            return;
        }
        for (int i = start; i < buckets.length; i++) {
            if(buckets[i]==0){
                continue;
            }
            if(target<i){
                continue;
            }
            buckets[i]--;
            stack.push(i);
            dfs2(buckets,target-i,i,stack,result);
            stack.pop();
            buckets[i]++;
        }
    }

    public static void main(String[] args) {
        int[] candidate = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        List<List<Integer>> lists = new leetcode40().combinationSum3(candidate, target);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }
}
